#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<sys/time.h>
using namespace std;
const int N = 10000, M = N*N;
int thread_count=7;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
typedef pair<int, int> PII;
int st[N], dist[N];
int main(int argc,char** args) {
	thread_count=args[1][0]-'0';
	memset(dist, 0x3f, sizeof dist);
	memset(h, -1, sizeof h);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	priority_queue<PII, vector<PII>, greater<PII> >heap;
	dist[1] = 0;
	heap.push({ 0,1 });



    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	while (!heap.empty())
	{
		auto head = heap.top();
		heap.pop();
		int v = head.second, d = head.first;
		if (st[v])continue;
		st[v] = 1;
		int i = h[v];
#pragma omp parallel num_threads(thread_count)
		{
#pragma omp single nowait
				while (~i) 
				{
#pragma omp task firstprivate(i)
					{
						int j = e[i];
						if (dist[j] > dist[v] + w[i]) 
						{
							dist[j] = dist[v] + w[i];
#pragma omp critical
							heap.push({ dist[j],j });
						}
					}
					i = ne[i];
				}
		}
	}
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}